# encoding:utf-8
class ListNode:
    """双向链表节点"""

    def __init__(self, val: int):
        """"""
        self.val: int = val
        self.next: ListNode | None = None
        self.prev: ListNode | None = None


class LinkedListDeque:
    """基于双向链表实现的双端队列"""

    def __init__(self):
        """构造方法"""
        self.__front: ListNode | None = None  # 头节点 front
        self.__rear: ListNode | None = None   # 尾节点 rear
        self.__size: int = 0                  # 队列的长度

    def size(self) -> int:
        """获取队列的长度"""
        return self.__size

    def is_empty(self) -> bool:
        """判断队列是否为空"""
        return self.__size == 0

    def push(self, num: int, is_front: bool) -> None:
        """入队操作"""
        node = ListNode(num)
        # 若链表为空，则令 front, rear 都指向 node
        if self.is_empty():
            self.__front = self.__rear = node
        # 队首入队操作
        elif is_front:
            # 将 node 添加至链表头部
            self.__front.prev = node
            node.next = self.__front
            self.__front = node  # 更新头节点
        # 队尾入队操作
        else:
            # 将 node 添加至链表尾部
            self.__rear.next = node
            node.prev = self.__rear
            self.__rear = node   # 更新尾节点
        self.__size += 1  # 更新队列长度

    def push_first(self, num: int) -> None:
        """队首入队"""
        self.push(num, True)

    def push_last(self, num: int) -> None:
        """队尾入队"""
        self.push(num, False)

    def pop(self, is_front: bool) -> int:
        """出队操作"""
        # 若队列为空，直接返回 -1
        if self.is_empty():
            return -1
        # 队首出队操作
        if is_front:
            val: int = self.__front.val
            # 删除头节点
            fnext: ListNode | None = self.__front.next
            if fnext != None:
                fnext.prev = None
                self.__front.next = None
            self.__front = fnext
            # 队尾出队操作
        else:
            val: int = self.__rear.val
            # 删除尾节点
            pre: ListNode | None = self.__rear.prev
            if pre!= None:
                pre.next = None
                self.__rear.prev = None
            self.__rear = pre
        self.__size -= 1
        return val

    def pop_first(self) -> int:
        """队首出队"""
        return self.pop(True)

    def pop_last(self) -> int:
        """队尾出队"""
        return self.pop(False)

    def peek_first(self) -> int:
        """访问队首元素"""
        return self.__front.val if self.__size > 0 else -1

    def peek_last(self) -> int:
        """访问队尾元素"""
        return self.__rear.val if self.__size > 0 else -1

    def to_list(self) -> list[int]:
        """返回列表用于打印"""
        node: ListNode | None = self.__front
        res: list[int] = [0] * self.__size
        for i in range(0, self.__size):
            res[i] = node.val
            node = node.next
        return res